home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / mint / gcc / gcc261c.zoo / objects / collhash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-18  |  5.5 KB  |  171 lines
  1. /* Hash tables for Objective C method dispatch, modified for libcoll.
  2.    Copyright (C) 1993,1994 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU CC is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. /* As a special exception, if you link this library with files
  21.    compiled with GCC to produce an executable, this does not cause
  22.    the resulting executable to be covered by the GNU General Public License.
  23.    This exception does not however invalidate any other reasons why
  24.    the executable file might be covered by the GNU General Public License.  */
  25.  
  26.  
  27. #ifndef __collhash_INCLUDE_GNU
  28. #define __collhash_INCLUDE_GNU
  29.  
  30. #ifdef IN_GCC
  31. #include "gstddef.h"
  32. #else
  33. #include "stddef.h"
  34. #endif
  35.  
  36. #include <objects/elt.h>
  37.  
  38. /* This returns an unsigned int that is the closest power of two greater 
  39.    than the argument. */
  40. /* If we can rely on having ffs() we could do this better */
  41. #define POWER_OF_TWO(n) \
  42. ({ \
  43.   unsigned _MASK = 1; \
  44.   while (n > _MASK) \
  45.     _MASK <<= 1; \
  46.   _MASK; \
  47. })
  48.  
  49.  
  50. /*
  51.  * This data structure is used to hold items
  52.  *  stored in a hash table.  Each node holds 
  53.  *  a key/value pair.
  54.  *
  55.  * Items in the cache are really of type void *.
  56.  */
  57. typedef struct coll_cache_node
  58. {
  59.   struct coll_cache_node *next;    /* Pointer to next entry on the list.
  60.                    NULL indicates end of list. */
  61.   elt key;            /* Key used to locate the value.  Used
  62.                    to locate value when more than one
  63.                    key computes the same hash
  64.                    value. */
  65.   elt value;            /* Value stored for the key. */
  66. } *coll_node_ptr;
  67.  
  68.  
  69. /*
  70.  * This data type is the function that computes a hash code given a key.
  71.  * Therefore, the key can be a pointer to anything and the function specific
  72.  * to the key type. 
  73.  *
  74.  * Unfortunately there is a mutual data structure reference problem with this
  75.  * typedef.  Therefore, to remove compiler warnings the functions passed to
  76.  * hash_new will have to be casted to this type. 
  77.  */
  78. typedef unsigned int (*coll_hash_func_type)(elt);
  79.  
  80. /*
  81.  * This data type is the function that compares two hash keys and returns an
  82.  * integer greater than, equal to, or less than 0, according as the first
  83.  * parameter is lexico-graphically greater than, equal to, or less than the
  84.  * second. 
  85.  */
  86.  
  87. typedef int (*coll_compare_func_type)(elt, elt);
  88.  
  89.  
  90. /*
  91.  * This data structure is the cache.
  92.  *
  93.  * It must be passed to all of the hashing routines
  94.  *   (except for new).
  95.  */
  96. typedef struct coll_cache
  97. {
  98.   /* Variables used to implement the hash itself.  */
  99.   coll_node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  100.   /* Variables used to track the size of the hash table so to determine
  101.     when to resize it.  */
  102.   unsigned int size; /* Number of buckets allocated for the hash table
  103.             (number of array entries allocated for
  104.             "node_table").  Must be a power of two.  */
  105.   unsigned int used; /* Current number of entries in the hash table.  */
  106.   unsigned int mask; /* Precomputed mask.  */
  107.  
  108.   /* Variables used to implement indexing through the hash table.  */
  109.  
  110.   /* commented out by mccallum */
  111.   /* unsigned int last_bucket; Tracks which entry in the array where
  112.                    the last value was returned.  */
  113.   /* Function used to compute a hash code given a key. 
  114.      This function is specified when the hash table is created.  */
  115.   coll_hash_func_type    hash_func;
  116.   /* Function used to compare two hash keys to see if they are equal.  */
  117.   coll_compare_func_type compare_func;
  118. } *coll_cache_ptr;
  119.  
  120.  
  121. /* Two important hash tables.  */
  122. /* This should be removed
  123. extern coll_cache_ptr module_hash_table, class_hash_table;
  124. */
  125.  
  126. /* Allocate and initialize a hash table.  */ 
  127.  
  128. coll_cache_ptr coll_hash_new (unsigned int size,
  129.             coll_hash_func_type hash_func,
  130.             coll_compare_func_type compare_func);
  131.                        
  132. /* Deallocate all of the hash nodes and the cache itself.  */
  133.  
  134. void coll_hash_delete (coll_cache_ptr cache);
  135.  
  136. /* Deallocate all of the hash nodes.  */
  137.  
  138. void coll_hash_empty (coll_cache_ptr cache);
  139.  
  140. /* Add the key/value pair to the hash table.  If the
  141.    hash table reaches a level of fullnes then it will be resized. 
  142.                                                    
  143.    assert if the key is already in the hash.  */
  144.  
  145. void coll_hash_add (coll_cache_ptr *cachep, elt key, elt value);
  146.      
  147. /* Remove the key/value pair from the hash table.  
  148.    assert if the key isn't in the table.  */
  149.  
  150. void coll_hash_remove (coll_cache_ptr cache, elt key);
  151.  
  152. /* Used to index through the hash table.  Start with NULL
  153.    to get the first entry.
  154.                                                   
  155.    Successive calls pass the value returned previously.
  156.    ** Don't modify the hash during this operation *** 
  157.                                                   
  158.    Cache nodes are returned such that key or value can
  159.    be extracted.  */
  160.  
  161. coll_node_ptr coll_hash_next (coll_cache_ptr cache, void** state);
  162.  
  163. /* Used to return a value from a hash table using a given key.  */
  164.  
  165. elt coll_hash_value_for_key (coll_cache_ptr cache, elt key);
  166.  
  167.  
  168. extern coll_node_ptr coll_hash_node_for_key (coll_cache_ptr cache, elt key);
  169.  
  170. #endif /* not __hash_INCLUDE_GNU */
  171.